import java.util.ArrayList;
import java.util.List;

// 猫鱼分干
public class cat {
    public static int solution(int n, List<Integer> catsLevels) {
        int[] fishCount = new int[n];

        // 初始化每只猫至少分配一斤鱼干
        for (int i = 0; i < n; i++) {
            fishCount[i] = 1;
        }

        // 从左到右遍历，确保等级高的猫比左边的猫得到更多鱼干
        for (int i = 1; i < n; i++) {
            if (catsLevels.get(i) > catsLevels.get(i-1)) {
                fishCount[i] = fishCount[i-1] + 1;
            }
        }

        // 从右到左遍历，确保等级高的猫比右边的猫得到更多鱼干
        for (int i = n - 2; i >= 0; i--) {
            if (catsLevels.get(i) > catsLevels.get(i+1) && fishCount[i] <= fishCount[i+1]) {
                fishCount[i] = fishCount[i+1] + 1;
            }
        }

        // 计算总的鱼干数量
        int totalFish = 0;
        for (int fish : fishCount) {
            totalFish += fish;
        }

        return totalFish;
    }

    public static void main(String[] args) {
        List<Integer> catsLevels1 = new ArrayList<>();
        catsLevels1.add(1);
        catsLevels1.add(2);
        catsLevels1.add(2);
        List<Integer> catsLevels2 = new ArrayList<>();
        catsLevels2.add(6);
        catsLevels2.add(5);
        catsLevels2.add(4);
        catsLevels2.add(3);
        catsLevels2.add(2);
        catsLevels2.add(16);
        List<Integer> catsLevels3 = new ArrayList<>();
        catsLevels3.add(1);
        catsLevels3.add(2);
        catsLevels3.add(2);
        catsLevels3.add(3);
        catsLevels3.add(3);
        catsLevels3.add(20);
        catsLevels3.add(1);
        catsLevels3.add(2);
        catsLevels3.add(3);
        catsLevels3.add(3);
        catsLevels3.add(2);
        catsLevels3.add(1);
        catsLevels3.add(5);
        catsLevels3.add(6);
        catsLevels3.add(6);
        catsLevels3.add(5);
        catsLevels3.add(5);
        catsLevels3.add(7);
        catsLevels3.add(7);
        catsLevels3.add(4);
        System.out.println(solution(3, catsLevels1) == 4);
        System.out.println(solution(6, catsLevels2) == 17);
        System.out.println(solution(20, catsLevels3) == 35);
    }
}